package 链表;

import list.ListNode;

/**
 * 143. 重排链表
 * 给定一个单链表 L 的头节点 head ，单链表 L 表示为：
 * L0 → L1 → … → Ln - 1 → Ln
 * 请将其重新排列后变为：
 * L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …
 * 不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
 *
 * 示例 1:
 * 输入: head = [1,2,3,4]
 * 输出: [1,4,2,3]
 * 示例 2:
 * 输入: head = [1,2,3,4,5]
 * 输出: [1,5,2,4,3]
 * 提示：
 * 链表长度范围为 [1, 5 * 104]
 * 链表中节点数目在范围 [1, 5 * 104] 内
 * 1 <= node.val <= 5 * 104
 *
 *  @author macy
 *  @date 2025/11/3 16:40
 */
public class ReOrderListNode {

    public static void main(String[] args) {

    }

    public void reorderList(ListNode head) {

        if(head==null || head.next==null){
            return ;
        }

        //找到中间节点
        ListNode mid = findMid(head);
        //中间节点-最后节点 进行反转
        ListNode last = reverseList(mid);
        ListNode p = head;
        // 拼接
        while(last.next !=null){
            ListNode next = p.next;
            ListNode next2 = last.next;
            p.next = last;
            last.next = next;
            p = next;
            last = next2;
        }
    }


    //找到中间节点
    public ListNode findMid(ListNode head){
        ListNode slow = head;
        ListNode fast = head;
        while(fast!=null && fast.next!=null){
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }


    //反转链表
    public ListNode reverseList(ListNode head) {

        ListNode pre = null;
        ListNode cur = head;
        while(cur!=null){
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }

}
